package com.ting.test.algorithms.strings;

/**
 * Created by 雷霆 on 2021/1/11.
 * <p>
 * Description：
 * 给定两个长度都为N的数组weights和values，
 * weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，
 * 你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 * <p>
 * 思路1：
 * 假设当前位置是index 那么index+1之后的所有物品都已经尝试装入了背包中
 * 也就是说 index+1 到 n的物品 都匹配完了
 * 获得的最优的总的重量和价值都已知
 * 那么需要考虑把当前index的物品放入背包或者不放入背包会出现什么情况
 * 即 把当前的物品加入背包或者不加入背包 哪一种情况获得的价值最大
 * 也就获得了 从 index到 n所有物品的最优解（最大价值）
 */
public class BeiBao {


    public static void main(String[] args) {

    }


    /**
     * @param index        当前匹配的货物
     * @param restCapacity 背包剩余的容量
     * @return index~n的货物能够匹配到的最佳的货物总的价值
     */
    public static int process2(int index, int[] weights, int[] values, int restCapacity) {
        //如果当前index已经到最后，则终止
        if (index == weights.length) {
            return -1;
        }
        //如果当前背包已经装的货物-当前index位置的货物质量超过背包容量，则 表示该货物不能放进去
        if ((restCapacity - weights[index]) < 0) {
            return 0;
        }

        //表示不加当前index所在位置的货物质量，所得到的index~n的价值
        int nextTotalValue = process2(index + 1, weights, values, restCapacity);
        //表示加当前index所在位置的货物质量，所得到的index~n的价值
        int nextPlusTotalValue = process2(index + 1 + weights[index], weights, values, restCapacity - weights[index]);
        nextPlusTotalValue = nextPlusTotalValue + values[index];
        return Math.max(nextPlusTotalValue, nextTotalValue);
    }

    /**
     * @param index       当前匹配的货物
     * @param totalWeight 截止目前背包总的质量
     * @return index~n的货物能够匹配到的最佳的货物总的价值
     */
    public static int process(int index, int totalWeight, int totalValue, int[] weights, int[] values, int bagCapacity) {
        //如果当前index已经到最后，则终止
        if (index == weights.length - 1) {
            //如果当前背包已经装的货物加上当前index位置的货物质量超过背包容量，则 表示该货物不能放进去
            if ((totalWeight + weights[index]) > bagCapacity) {
                return totalValue - values[index];
            }else{
                return totalValue;
            }
        }


        //表示不加当前index所在位置的货物质量，所得到的index~n的价值
        int nextTotalValue = process(index + 1, totalWeight, totalValue, weights, values, bagCapacity);
        //表示加当前index所在位置的货物质量，所得到的index~n的价值
        int nextPlusTotalValue = process(index + 1, totalWeight + weights[index], totalValue + values[index], weights, values, bagCapacity);
        return Math.max(nextPlusTotalValue, nextTotalValue);
    }
}
